package com.cat.DataStructure04;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/number-of-digit-one/
 * @create 2025/11/25 14:23
 * @since JDK17
 */

public class Solution07 {
    int N = 11;
    int[][] dp = new int[N][N];
    int dfs(char[] num, int i, int one, boolean isNum, boolean free) {
        if (num.length == i) {
            return isNum ? one : 0;
        }
        if (isNum && free && dp[i][one] != -1) {
            return dp[i][one];
        }
        int ans = 0, up = free ? 9 : num[i] - '0';
        if (!isNum) {
            ans = dfs(num, i + 1, one, false, true);
        }
        for (int j = isNum ? 0 : 1; j <= up; j++) {
            ans += dfs(num, i + 1, one + (j == 1 ? 1 : 0), true, free || j < up);
        }
        if (isNum && free) {
            dp[i][one] = ans;
        }
        return ans;
    }
    public int countDigitOne(int n) {
        for (int i = 0; i < N; i++) {
            Arrays.fill(dp[i], -1);
        }
        return dfs(String.valueOf(n).toCharArray(), 0, 0, false, false);
    }
}
